package crazy.tree;

import java.util.ArrayList;
import java.util.List;



public class TreeChild<T>
{
	private static class SonNode
	{
		private int pos;
		private SonNode next;
		
		public SonNode(int pos, SonNode next)
		{
			this.pos = pos;
			this.next = next;
		}
	}
	
	public static class Node<T>
	{
		T data;
		SonNode first;
		
		public Node(T data)
		{
			this.data = data;
			this.first = null;
		}
		
		public String toString()
		{
			if (first != null)
			{
				return "TreeChild$Node[data=" + data + ", first="+first.pos+"]";
			}
			else
			{
				return "TreeChild$Node[data=" +data + ", first=-1]";
			}
		}
	}
	
	private final int DEFAULT_TREE_SIZE = 100;
	private int treeSize = 0;
	private Node<T>[] nodes;
	private int nodeNums;
	
	public TreeChild(T data)
	{
		treeSize = DEFAULT_TREE_SIZE;
		nodes = new Node[treeSize];//定义array大小，不用指定数据类型，所以可以直接用Node
		nodes[0] = new Node<T>(data);//为array[0]指定值，需要说明值的类型Node<T>
		nodeNums++;
	}
	
	public TreeChild(T data, int treeSize)
	{
		this.treeSize = treeSize;
		nodes = new Node[treeSize];
		nodes[0] = new Node<T>(data);
		nodeNums++;
	}
	
	public void addNode(T data, Node parent)
	{
		for (int i = 0; i < treeSize; i++)
		{
			if (nodes[i] == null)
			{
				nodes[i] = new Node<T>(data);//先添加一个节点在树上。
				if (parent.first == null) //将该新增的节点的index 加到它的parent的子节点链上
				{
					parent.first = new SonNode(i, null);
				}
				else 
				{
					SonNode next = parent.first;
					while (next.next != null)
					{
						next = next.next;
					}
					next.next = new SonNode(i, null);
				}
				nodeNums++;
				return;
			}
		}
		throw new RuntimeException("tree is full");
	}
	
	public boolean empty()
	{
		return nodes[0] == null;
	}
	
	public Node<T> root()
	{
		return nodes[0];
	}
	
	public List<Node<T>> children(Node parent)
	{
		List<Node<T>> list = new ArrayList<Node<T>>();
		SonNode next = parent.first;
		while (next != null)
		{
			list.add(nodes[next.pos]);
			next = next.next;
		}
		return list;
	}
	
	public Node<T> child(Node parent, int index)
	{
		SonNode next = parent.first;
		for (int i = 0; next != null; i++)
		{
			if (index == i)
			{
				return nodes[next.pos];
			}
			next = next.next;
		}
		return null;
	}
	
	public int deep()
	{
		return deep(root());
	}
	
	public int deep(Node node)
	{
		if (node.first == null)
		{
			return 1;
		}
		else
		{
			int max = 0;
			SonNode next = node.first;
			while (next != null)
			{
				int tmp = deep(nodes[next.pos]);
				if (tmp > max)
				{
					max = tmp;
				}
				next = next.next;
			}
			return max + 1;
		}
	}
	
	public int pos(Node node)
	{
		for (int i = 0; i < treeSize; i++)
		{
			if (nodes[i] == node)
			{
				return i;
			}
		}
		return -1;
	}
}
